package cn.njupt.tree;
import cn.njupt.util.Comparator;

//二叉搜索树
public class BST<E> extends BinaryTree<E>{

    private Comparator<E> comparator;

    public BST() {
        this(null);
    }

    public BST(Comparator<E> comparator) {
        this.comparator = comparator;
    }


    /**
     * 向二叉搜索树中添加节点
     * @param element
     */
    public void add(E element) {
        elementCheckIsNull(element);
        if (root == null) {
            this.root = createNode(element, null);
            afterAdd(root);
            size++;
            return;
        }
        Node<E> cur = root;
        Node<E> parent = null;
        int cmp = 0;
        while (cur != null) {
            parent = cur;
            cmp = compare(cur.element, element);
            if (cmp > 0) {  //右子树
                cur = cur.left;
            } else if (cmp < 0) {//左子树
                cur = cur.right;
            } else {
                cur.element = element;
                return;
            }
        }
        Node<E> node = createNode(element, parent);
        if (cmp > 0) {
            parent.left = node;
        } else {
            parent.right = node;
        }
        size++;
        afterAdd(node);
    }

    protected void afterAdd(Node<E> node){

    }

    /**
     * 删除node之后的调整
     * @param node 被删除的节点
     */
    protected void afterRemove(Node<E> node){

    }

    public int compare(E e1, E e2) {
        if (comparator != null) {
            return this.comparator.compare(e1, e2);
        }
        return ((Comparable) e1).compareTo(e2);
    }

    public void elementCheckIsNull(E element) {
        if (element == null) {
            throw new IllegalArgumentException("传递的参数为空");
        }
    }

    public void remove(E element) {
        remove(node(element));
    }

    private void remove(Node<E> node) {
        if(node==null) return;

        if(node.hasTwoChildren()){
            Node<E> pre=getPreceNode(node);//得到前驱节点
            node.element=pre.element;
            //删除pre
            node=pre;
        }
        Node<E> replacement=node.left==null?node.right:node.left;
        if(replacement!=null){ //度为1
            //判断左子树还是右子树
            if(node.parent==null){
                root=replacement;
                replacement.parent=node.parent;
            }else if(node==node.parent.left){ //左子树
                node.parent.left=replacement;
                replacement.parent=node.parent;
            }else{  //右子树
                node.parent.right=replacement;
                replacement.parent=node.parent;
            }
        }else{ //度为0
            if(node.parent==null){
                root=null;
            }else if(node.parent.left==node){
                node.parent.left=null;
            }else{
                node.parent.right=null;
            }

        }
        afterRemove(node);
        size--;
    }


    public Node<E> node(E element){
        Node<E> node=root;
        while(node!=null){
            int cmp=compare(node.element,element);
            if(cmp==0)return node;
            if(cmp>0){ //说明应该往左子树查询
                node=node.left;
            }else{ //说明应该往右子树查询
                node=node.right;
            }
        }
        return null;
    }




    public boolean contains(E element) {
        return node(element)!=null;
    }





}
